Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

  1. nums1 = [1, 3]
  2. nums2 = [2]
  4. The median is 2.0

Example 2:

  1. nums1 = [1, 2]
  2. nums2 = [3, 4]
  4. The median is (2 + 3)/2 = 2.5

Solution:

  1. public class Solution {
  2.   public double findMedianSortedArrays(int[] nums1, int[] nums2) {
  3.     int l1 = nums1.length;
  4.     int l2 = nums2.length;
  6.     int k = (l1 + l2) / 2;
  8.     if ((l1 + l2) % 2 == 0) {
  9.       return (helper(nums1, 0, l1 - 1, nums2, 0, l2 - 1, k) + helper(nums1, 0, l1 - 1, nums2, 0, l2 - 1, k + 1)) / 2.0;
  10.     } else {
  11.       return helper(nums1, 0, l1 - 1, nums2, 0, l2 - 1, k + 1);
  12.     }
  13.   }
  15.   double helper(int[] a1, int i1, int j1, int[] a2, int i2, int j2, int k) {
  16.     int l1 = j1 - i1 + 1;
  17.     int l2 = j2 - i2 + 1;
  19.     if (l1 > l2) {
  20.       return helper(a2, i2, j2, a1, i1, j1, k);
  21.     }
  23.     if (l1 == 0) {
  24.       return a2[i2 + k - 1];
  25.     }
  27.     if (k == 1) {
  28.       return Math.min(a1[i1], a2[i2]);
  29.     }
  31.     int n1 = Math.min(k / 2, l1);
  32.     int n2 = k - n1;
  34.     int v1 = a1[i1 + n1 - 1];
  35.     int v2 = a2[i2 + n2 - 1];
  37.     if (v1 == v2) {
  38.       return v1;
  39.     } else if (v1 < v2) {
  40.       return helper(a1, i1 + n1, j1, a2, i2, i2 + n2 - 1, k - n1);
  41.     } else {
  42.       return helper(a1, i1, i1 + n1 - 1, a2, i2 + n2, j2, k - n2);
  43.     }
  44.   }
  45. }